BZOJ2152 聪聪可可 <点分治>

Problem

聪聪可可

Description

聪聪和可可是兄弟俩，他们俩经常为了一些琐事打起来，例如家中只剩下最后一根冰棍而两人都想吃、两个人都想玩儿电脑（可是他们家只有一台电脑）……遇到这种问题，一般情况下石头剪刀布就好了，可是他们已经玩儿腻了这种低智商的游戏。他们的爸爸快被他们的争吵烦死了，所以他发明了一个新游戏：由爸爸在纸上画个“点”，并用条“边”把这个“点”恰好连通（其实这就是一棵树）。并且每条“边”上都有一个数。接下来由聪聪和可可分别随即选一个点（当然他们选点时是看不到这棵树的），如果两个点之间所有边上数的和加起来恰好是的倍数，则判聪聪赢，否则可可赢。聪聪非常爱思考问题，在每次游戏后都会仔细研究这棵树，希望知道对于这张图自己的获胜概率是多少。现请你帮忙求出这个值以验证聪聪的答案是否正确。

Input

输入的第行包含个正整数。后面行，每行个整数、、，表示号点和号点之间有一条边，上面的数是。

Output

以即约分数形式输出这个概率（即“”的形式，其中和必须互质。如果概率为，输出“”）。

Sample Input

Sample Output

13/25

Hint

样例说明
共组点对分别是。
数据规模
对于的数据，。

标签：点分治

Solution

经典点分治例题。
对于每个点，只考虑经过它的符合条件的路径，统计后递归分治左右子树。
这样我们只需要计算经过指定点长度为的倍数的路径即可。
不难发现我们只需分别统计模余的一段在指定点的路径条数即可。
统计后，设三种余数的条数为, , ，则答案为。

Code

#include <bits/stdc++.h>
#define MAX_N 200000
using namespace std;
int n, rt, tot, ans;	vector <int> G[MAX_N+5], E[MAX_N+5];
int s[MAX_N+5], h[MAX_N+5], dep[MAX_N+5], cnt[3];	bool mrk[MAX_N+5];
void addedge(int u, int v, int c) {G[u].push_back(v), E[u].push_back(c%3);}
int gcd(int a, int b) {return b ? gcd(b, a%b) : a;}
int frac(int a, int b) {return a/gcd(a, b);}
void getrt(int u, int fa) {
    s[u] = 1, h[u] = 0;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i];	if (v == fa || mrk[v]) continue;
        getrt(v, u);	s[u] += s[v], h[u] = max(h[u], s[v]);
    }
    h[u] = max(h[u], tot-s[u]);
    if (h[u] < h[rt])	rt = u;
}
void getdep(int u, int fa) {
    cnt[dep[u]]++;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];
        if (v == fa || mrk[v]) continue;
        dep[v] = (dep[u]+c)%3, getdep(v, u);
    }
}
int calc(int u, int init) {
    cnt[0] = cnt[1] = cnt[2] = 0;
    dep[u] = init, getdep(u, 0);
    return cnt[0]*cnt[0]+cnt[1]*cnt[2]*2;
}
void DFS(int u) {
    ans += calc(u, 0), mrk[u] = true;
    for (int i = 0; i < (int)G[u].size(); i++) {
        int v = G[u][i], c = E[u][i];	if (mrk[v])	continue;
        ans -= calc(v, c), rt = 0, tot = s[v], getrt(v, 0), DFS(rt);
    }
}
int main() {
    scanf("%d", &n);	for (int i = 1, u, v, c; i < n; i++) scanf("%d%d%d", &u, &v, &c), addedge(u, v, c), addedge(v, u, c);
    tot = h[0] = n, getrt(1, 0), DFS(rt);	printf("%d/%d", frac(ans, n*n), frac(n*n, ans));	return 0;
}